package cn.edu.jxau.test;

import java.util.Objects;
import java.util.concurrent.ExecutionException;

public class Main {

	public static void main(String[] args) throws InterruptedException, ExecutionException {

//		int[] arr = new int[] { 5, 7, 6, 9, 11, 10, 8 };
		int[] arr = new int[] { 7, 4, 6, 5 };
		System.out.println(isPostOrderOfBT(arr));
	}

	public static boolean isPostOrderOfBT(int[] arr) {

		Objects.requireNonNull(arr, "参数arr不能为null");
		if (arr.length == 0) {
			throw new IllegalArgumentException("参数arr为空数组");
		}
		return isPostOrderOfBT(arr, 0, arr.length - 1);
	}

	public static boolean isPostOrderOfBT(int[] arr, int low, int high) {

		if (low >= high) {
			return true;
		}
		int root = arr[high];
		int i = 0;
		for (; i < high; i++) {
			if (arr[i] > root) {
				break;
			}
		}
		int j = i;
		for (; j < high; j++) {
			if (arr[j] < root) {
				return false;
			}
		}
		boolean left = true;
		if (i > 0) {
			left = isPostOrderOfBT(arr, low, i - 1);
		}
		boolean right = true;
		if (i < high) {
			right = isPostOrderOfBT(arr, i, high - 1);
		}
		return left & right;
	}
}

class Node<T> {

	public T data;
	public Node<T> right;
	public Node<T> left;

	public Node(T data) {
		this.data = data;
	}
}